/**
 * [29] Divide Two Integers
 *
 * Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
 *
 * Return the quotient after dividing dividend by divisor.
 *
 * The integer division should truncate toward zero.
 *
 * Example 1:
 *
 *
 * Input: dividend = 10, divisor = 3
 * Output: 3
 *
 * Example 2:
 *
 *
 * Input: dividend = 7, divisor = -3
 * Output: -2
 *
 * Note:
 *
 *
 * 	Both dividend and divisor will be 32-bit signed integers.
 * 	The divisor will never be 0.
 * 	Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-2^31,  2^31 - 1]. For the purpose of this problem, assume that your function returns 2^31 - 1 when the division result overflows.
 *
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/divide-two-integers/
// discuss: https://leetcode.com/problems/divide-two-integers/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

//a <=0, b < 0
fn div(a: i32, b: i32) -> i32 {
    assert!(a <= 0 && b < 0);
    if a > b {
        return 0;
    }
    let mut q = 1;
    let mut tb = b;
    while tb > (i32::MIN >> 1) && (tb + tb) > a {
        q += q;
        tb += tb;
    }
    q + div(a - tb, b)
}

impl Solution {
    pub fn divide(dividend: i32, divisor: i32) -> i32 {
        let mut a = dividend;
        let mut b = divisor;
        // overflow if a=i32::MIN and b=-1
        if a == i32::MIN && b == -1 {
            return i32::MAX;
        }
        // change a and b into negative, since abs(i32:MIN)>abs(i32:MAX)
        let mut sign = 1;
        if a > 0 {
            a = -a;
            sign = -sign;
        }
        if b > 0 {
            b = -b;
            sign = -sign;
        }
        sign * div(a, b)
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_29() {
        assert_eq!(3, Solution::divide(10, 3));
        assert_eq!(-2, Solution::divide(7, -3));
    }
}
